The present invention relates to a memory for information search through a prefix analysis, devoted in particular to building routing tables for high speed communication networks, preferably for the Internet network.
Communication protocols for modern high speed networks, such as the ATM networks, the Internet network etc., are based on the transmission of information packets containing, in the header, information relating to the destination address of the packet. In a node of the network, when receiving a packet, the routing control units use the address to perform a search inside a suitable table or data base and to locate the output interface to which the packet must be supplied for further forwarding to a successive network unit. Presently, transmission rates of the order of the Gbits/s are common and therefore routing time in a node must be very short to prevent impairing regular traffic flow. To provide a quantitative indication, it must be considered that a 1 Gbit/s transmission with packets of about 1000 bits requires for the nodes to handle about 1 million packets per second. Taking into account the switching time, the time necessary for possible packet header processing and possible guard times between consecutive packets, the search in the routing table, which is the longest operation, must be performed in a time somewhat less than 1 xcexcs. The situation becomes more critical with increasing communication speed.
Referring for simplicity of description and just as an example to the Internet network, there is an exponential growth of both the number of host computers connected to the network and the traffic, as well as of the band requirements, also due to the continuous development of new applications using the Internet network. All this results in an increase in the routing table size, which causes in turn a longer search operation. Now it is well known to the technicians that, while it is easier and easier to have high memory capacity at low cost, reduction of access time to large memories involves considerable technological problems.
In order to have an easier adaptation to the network expansion, the Internet addresses can be organized according to a hierarchical structure, in the sense that groups of addresses corresponding e.g. to the same geographical region or to the same provider share the most significant address bits (prefix). These prefixes have variable lengths and can in turn constitute the most significant part of other prefixes (prefixes of prefixes). Further details on the structure of the Internet addresses can be found for example in the documents xe2x80x9cDas Internet-Protokoll der nachsten Generationxe2x80x9d by H. P. Giesiger, Comtec 5, 1998, pages 20 to 26, or xe2x80x9cIP Next Generation Overviewxe2x80x9d, by R. M. Hinden, dated May 14, 1995 and available at the Internet site http:playground.sun. com/pub/ipng/html/INET-Ipng-Paper.html.
In order to reduce the search complexity, the routing information in the network is related above all to the address of a subsequent node in the path leading to the destination of the packet being processed. That address is commonly indicated with the term xe2x80x9cnext hopxe2x80x9d. Since the possible different next hops in a routing table may be of the order of a hundred, it is possible to extract the relevant information and store it into another data structure. Given the small dimensions, this structure can be accessed by using direct access through an index, designated in literature xe2x80x9cTARGETxe2x80x9d, which is identified starting from the address of the received packet. In practice, in a routing management unit, by using as a search key the packet destination address, access is gained to a forwarding table which is a subset of the complete routing table of a network and where each row contains a prefix (addressmask.pair, where the mask indicates the number of significant bits of the address, i.e. the bits constituting the prefix) and a corresponding data (the target, commonly a pointer to the output interface, together with further information). A prefix originates a match for the search key (i.e. it allows reaching a target) if the bit-by-bit AND of the key with the mask associated to the address is equal to the address itself.
The variability of the prefix lengths causes a further complication since the index search may result in retrieving several targets, since the comparison may give a positive result for several prefixes of different lengths. In these conditions the actual target is that corresponding to the longest prefix, i.e. the most specific one for the destination. This criterion is known as the xe2x80x9clongest prefix matchxe2x80x9d.
Theoretically, the most efficient and fastest method to perform a search based on the longest prefix match is storing the information items (entries) into one or more ternary CAMs (CAM=Content Addressable Memory). In a ternary CAM, each memory bit may assume three values: 0, 1 and (xe2x80x9cdon""t carexe2x80x9d). The comparison between the bits of the comparison register and the memory bits set at a xe2x80x9cdon""t carexe2x80x9d logic value obviously is always positive. It is therefore possible to implicitly implement the masks associated to a data by simply setting at don""t care level the relevant bits of the data itself. The drawback of this type of device mainly lies in the high price and poor integration capability.
In order for low cost conventional memories to be used, it is therefore necessary to utilize algorithms for searching in data bases which are both fast and compact. The speed of a search algorithm is strictly connected to the number of memory accesses, while the compactness is determined by the quantity of memory needed for storing the data structure being used. The final aim is that of minimizing as much as possible both the access number and the memory size required to store the information for the search process.
The practical implementations of the routing algorithms suitable for satisfying the criterion of the longest prefix match may be both of the software type and of the hardware type. In general, they must meet anyhow a certain number of common requirements such as:
search speed as independent as possible from the table dimensions;
small variance of algorithm performance between the worst case and the best case;
easy incremental (or localized) table updating (i.e. the insertion or cancellation of some information items should not require re-writing the entire table or substantial portions of the same);
flexibility, so as to-be easily adaptable to future technological developments and to variations in the address organization;
memory organization as regular as possible for preventing waste.
Several solutions have already been proposed for solving the problem of the Internet network routing in such a manner as to take into account the need of implementing the longest prefix match.
A first group of solutions is based on an algorithm known as xe2x80x9cPATRICIAxe2x80x9d, which is an algorithm for the storage, indexing and retrieval of information in large files, particularly catalogues of libraries. The principles of this algorithm are described in the article xe2x80x9cPATRICIAxe2x80x94Practical Algorithm To Retrieve Information Coded In Alphanumericxe2x80x9d, by D. R. Morrison, Journal of the Association for Computing Machinery, Vol. 15., No. 4, October 1968, pages 155 and following, and its application in solving routing problems in the Internet network is widely documented in the relevant technical literature. The PATRICIA algorithm is substantially an algorithm operating on a prefix tree, built on the address bits, where each bit corresponds to a node. The address bits are examined one at a time. To avoid examining nodes which correspond to nonexisting branches, each bit is associated to an indication of the successive bit to be examined. Once the search is over, a check is performed on the real existence of the prefix. Since each node corresponds to one or more memory access, and considering that the memory access is much slower than the data processing, the algorithm provides a real reduction of the total time for retrieving the address.
The essential disadvantage of the solutions based on the PATRICIA algorithm is that a practical implementation is to be calibrated on the worst case (in practice, the passage through all the tree nodes must be accounted for), while in the present Internet network it has been noticed that statistically about twenty nodes must be analyzed before reaching the target (the address searched for). Therefore, these solutions are intrinsically quite slow and present, in addition, a strong variance between the worst case and the typical case.
To accelerate the search process, some algorithms have been proposed where multiple address bits are taken into consideration at each search step along the tree instead of one bit only. The article xe2x80x9cPutting Routing Tables in Siliconxe2x80x9d, by T. Pei and C. Zukowski, IEEE Network Magazine, January 1992, page 42 and following, discloses how these algorithms can be implemented in hardware by means of the so called xe2x80x9ctrie memoriesxe2x80x9d. The main problem in this case is that the conventional trie memories can be utilized only if no multiple matches are present.
Therefore, many, proposals of algorithms intended for performing searches in routing tables for the Internet network in such a manner as to reduce the memory needed for the table or generally to fasten the search process, are based on restructuring the prefixes so as to eliminate the multiple matches. In this way the algorithms could be theoretically implemented with the use of trie memories.
Examples of restructuring of prefixes are described by M. Degemark et al in the paper xe2x80x9cSmall Forwarding Tables for Fast Routing Lookupsxe2x80x9d presented at the conference ACM SIGCOMM ""97, Cannes (France), Sep. 16-18, 1997, and by V. Srinivasan and G. Varghese in the paper xe2x80x9cFaster IP Lookups using Controlled Prefix Expansionxe2x80x9d presented at the conference ACM SIGMETRICS ""98, Madison (Wisconsin, USA), Jun. 22-26, 1998.
The solution proposed by Degemark et al leads to a three level tree where each level covers 16, 8 and 8 bits of the address, respectively, and is stored in a particularly compact structure, made possible by a suitable restructuring of prefixes, thanks to which each prefix in the tree locates an interval of addresses. This solution drastically minimizes the quantity of memory required and the access times to the memory itself for the search with respect to the solution based on PATRICIA (about 400 ns for the worst case that foresees 12 accesses); yet restructuring the prefixes makes the incremental updating impossible and requires the complete re-writing of the memory at each updating: the updating process then is very slow and may cause problems to the normal network management.
The solution proposed by V. Srinivasan and G. Varghese restructures the prefixes so that they only take a limited number of length values (possibly variable), and expands the shortest prefixes by substituting them with the set of prefixes having the closest predetermined length value. The routing table is transformed into a certain number of sub-tables each storing pointers to the successive sub-table, and the lengths of such sub-tables are optimized so as to obtain a reduction, for a given access number, of the memory needed for that specific set of prefixes. By this arrangement a reduction of the quantity of memory used is in general obtained, even though the table length generally is not predictable and then an optimum exploitation of the physical memory is not obtained. In addition, the resulting data structure is optimized for a specific set of prefixes and therefore it is scarcely general.
The present invention has as its object to provide a structure which guarantees an optimum exploitation of the physical memory and an incremental updating of the routing table (or in general of the set of entries).
The memory according to the invention comprises:
a memory element comprising a plurality of rows and columns of memory cells where each cell stores an item belonging to a set of information items, each information item being associated to a mask indicating a number of significant characters of a respective prefix and to a target constituting a data possibly utilizable for accessing a further set of information items, and
control devices for controlling the search for a specific information item in the memory and for updating the memory, said control devices operating through the comparison between successive portions, of pre-determined lengths, of a string of characters received at the input and corresponding portions of stored prefixes, said prefixes possibly having a variable length which is not a multiple of the length of said portions.
According to the invention for implementing a search criterion based on the longest prefix match:
each cell is subdivided into an information field, which stores dither a successive row address for continuing a search, or an information relating to a reached target, and a pair of flags which specify the contents of the information field, and
an auxiliary vector is provided, that presents as many cells as are the rows in said memory element and that, when the flags of one of said cells of the memory element indicate the reaching of a target together with the need of prosecuting the search into a successive row, is capable of storing the target information into the cell associated to said successive row, each cell of said auxiliary vector storing an information field and a pair of flags which have the same tasks as those of the cells of said memory element.
The invention concerns also a method for the management of the above mentioned memory.